1. Field of the Invention
This invention relates to a digital halftoning system, and more particularly to a digital halftoning system that iteratively diffuses error to reduce the formation of visible correlated patterns or artifacts.
2. Description of the Prior Art
Digital halftoning converts image information including a large number of gray scaled pixel values to a reduced number of gray scaled pixel values in order that image information be rendered for display or hardcopy (printed) output. Image information, be it color or black and white, is commonly derived by scanning, initially at least, in a gray level format containing a large number of gray density levels, e.g., 256 levels for black and white and more than 16 million (256.sup.3) levels for color, which is usually not reproducible on standard printing and display systems. The term "gray level" is used herein to described data for both black and white or color applications. For example, standard printing system print in a limited number of levels, either a spot or a no spot in the binary case, or a limited number of levels associated with the spot, such as four in the quaternary case. Thus, image information encoded by a large number of gray level values must be converted to a fewer number of gray level values in order that the image information be rendered on typical display and printing systems.
Digital halftoning techniques of converting gray level pixel image data to binary level pixel image data as described above may be divided into three categories; dithering, error diffusion, and optimization based methods. The dithering compares gray level values of pixels to be halftoned with a set of preselected thresholds, thereby converting gray level pixel image data to binary level pixel image data. In the error diffusion method, an error generated when a given pixel is binarized, is propagated to its neighboring pixels and reflected when the neighboring pixels are binarized. The optimization based halftoning method establishes a difference between gray level pixel image data and binary level pixel image data as error criterion, and then performs the binarization such that the error criterion is minimized by utilizing optimization techniques such as statistics, neural network, gene algorithm and so on. The present widespread halftoning methods are the dithering and the error diffusion method. The dithering is widely used because of a rapid speed characteristic while the error diffusion is widely used because of an excellent quality characteristic of output binary image.
Basic error diffusion method is proposed by Floyd and Steinberg, in "An Adaptive Algorithm fro Spatial Greyscale", Proceedings of the SID 17/2, 75-77 (1976). Binary level pixel image data obtained through the Floyd-Steinberg's error diffusion method, however, often exhibits undesirable artifacts at certain gray levels. In order to reduce the undesirable artifacts, methods of enhancing the neighboring pixels used upon error diffusion are suggested by Jarvis et al. and Stucki et al. In these methods, the error diffusion technique as taught in "A Survey of Techniques for the Display of Continuous Tone Pictures on Bi-level Displays" by Javis et al., Computer Graphics and Image Processing, Vol. 5., pp. 13-40 (1976) can reduce the artifacts, but has a disadvantage in that much calculation time is required. Alternative error diffusion techniques for reducing artifacts are taught in "Error Diffusion with a More Symmetric Error Distribution" (1994), by Fan, published at IS&T/SPIE Symposium regarding electronic image science and techniques, and in "Edge-enhanced Error Diffusion Method Employing Blue Noise Mask" (1994), by Jang-sik Park et al., published at the 7th Workshop regarding image processing and understanding. In these methods, new locations and coefficient values has been suggested for neighboring pixels that are to experience the error propagation. In addition to these methods, an attempt for the edge enhancement in binarized image is taught in "New Edge-enhanced Error Diffusion algorithm Based On the Error Sum Criterion", Electronic Image Journal (1995), by Jae-ho Kim.
However, when a certain pixel is binarized, all the above methods reflect only causal errors propagated from the previously quantized pixels in surrounding pixels of the certain pixel. The causal errors are errors generated from pixels located in the left and upper sides of a pixel to be quantized as the quantization is progressed from the left side into the right side and from the upper side into the lower side. On the other hand, non-causal errors contrary to the causal errors is errors to be produced upon quantization for pixels located in the right and lower sides of the pixel to be quantized. For example, Floyd-Steinberg's error diffusion method, Zhigang Fan's first error diffusion method, Zhigang Fan's second error diffusion method, Jang-sik Park's error diffusion method, Stucki's error diffusion method and Jarvis's error diffusion method, as shown in FIG. 1(A) to FIG. 1(F), respectively, reflect only causal errors propagated from pixels located in the left and upper sides of a certain pixel when the certain pixel is quantized. In other words, any causal errors are not reflected in a certain pixel binarized by the conventional error diffusion techniques. This results from a visible correlated patterns and/or artifacts exhibiting in binary level pixel image binarized using the conventional error diffusion pixels.